package a02_链表;

/**
 * <p>
 * a05_删除链表的倒数第N个节点
 * </p>
 *
 * @author flyduck
 * @since 2024-06-19
 */
public class a06_删除链表的倒数第N个节点复习2 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode listNode = removeNthFromEnd(head, 2);
        ListNode temp = listNode;
        while (temp != null) {
            System.out.println(temp.val);
            temp = temp.next;
        }
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        //删除倒数第n个，必须知道它的前一个，如果要删除第一个，就得特殊处理，需要引入虚拟节点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode slowNode = dummyNode;
        ListNode fastNode = dummyNode;
        //比如总共1个元素，要删除倒数第1个，那么快指针最后肯定移动到null，慢指针不动，那么快指针先要移动2次
        while (n >= 0) {//n=1，不能进入循环
            fastNode = fastNode.next;
            n--;
        }

        //然后一起移动
        while (fastNode != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }

        //此时slowNode就是前一个节点
        slowNode.next = slowNode.next.next;
        return dummyNode.next;
    }
}
